package edu.cuit.avatar.array;

import java.util.Arrays;

/**
 * 数组元素查找
 * @author <a href="mailto:1020zhaodan@163.com">Adan</a>
 * @version 1.0
 * @date 2025/7/3 14:58
 */
public class SearchArrayElement {
    /**
     * 线性查找关键字元素key在数组中的索引
     * 从数组的第一个元素依次的比较，如果该元素==关键字元素，返回该元素对应的索引。
     * @param key 关键字
     * @param list 数组
     * @return 如果查找到该元素，就返回该元素对应的索引，没有找到返回-1
     */
    public static int linear(int key, int[] list){
        for (int i = 0; i < list.length; i++) {
            if(list[i] == key)
                return i;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] list = {100, 30, 25, 18, 200, 156, -10, 0};
        System.out.println(linear(18, list)); // 3
        System.out.println(linear(200, list)); // 4

        //使用Arrays工具类中提供的排序方法对数组进行排序
        Arrays.sort(list);
        System.out.println(Arrays.toString(list));
        System.out.println(binarySearch(18, list));
        System.out.println(binarySearch(300, list));

        //使用Arrays工具类中提供的二分查找方法进行元素的查找
        System.out.println(Arrays.binarySearch(list, 18));
        System.out.println(Arrays.binarySearch(list, 300));
        System.out.println(Arrays.binarySearch(list, -200));
    }
    /**
     * 折半查找
     *      前提：数组是一个有序数组
     * 每次折半取中间元素
     * 1.如果关键字小于中间元素，只需要在数组的前一半进行查找
     * 2.如果关键字大于中间元素，只需要在数组的后一半进行查找
     * 3.相等，就返回mid
     */
    public static int binarySearch(int key, int[] list){
        int low = 0;
        int high = list.length - 1;

        while(low <= high){
            //计算每次折半的中间元素索引
            int mid = (low + high) / 2;
            if(list[mid] == key)
                return mid;
            else if(list[mid] > key)
                high = mid -1;
            else
                low = mid + 1;
        }
        return -low - 1;
    }
}
